package dynamic;

public class Ex221 {
   static class Solution {
       //惊了，这也能过。。。
        int m, n;
        public int maximalSquare1(char[][] matrix) {
            int m, n;
            if (matrix == null || (m = matrix.length) == 0 || (n = matrix[0].length) == 0) return 0;
            this.m = m;
            this.n = n;
            int max = 0;
            int[][] nums = new int[m][n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    nums[i][j] = matrix[i][j] - '0';
                }
            }
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (matrix[i][j] == '1') {
                        int size = findMaxLarge(nums, i, j);
                        if (size > max) {
                            max = size;
                            System.out.println(i + " " + j);
                        }
                    }
                }
            }
            return max * max;
        }

        public int findMaxLarge(int[][] nums, int x, int y) {
            int cur = 1;
            while (true) {
                int xm = x + cur, ym = y + cur;
                for (int i = x; i < xm; i++) {
                    for (int j = y; j < ym; j++) {
                        if (i >= m || j >= n || nums[i][j] != 1) return cur - 1;
                    }
                }
                cur++;
            }
            
        }

        public int maximalSquare(char[][] matrix) {
            int m, n;
            if (matrix == null || (m = matrix.length) == 0 || (n = matrix[0].length) == 0) return 0;
            int[][] f = new int[m][n];
            for (int i = 0; i < m; i++) {
                if (matrix[i][0] == '1') f[i][0] = 1;
            }
            for (int j = 0; j < n; j++) {
                if (matrix[0][j] == '1') f[0][j] = 1;
            }
            int max = 1;
            for (int i = 1; i < m; i++) {
                for (int j = 1; j < n; j++) {
                    if (matrix[i][j] == '0') f[i][j] = 0;
                    else {
                        if (f[i - 1][j - 1] == 0) f[i][j] = 1;
                        else {
                            int len = (int)Math.sqrt(f[i - 1][j - 1]), l = 0;
                            for (int k = 0; k <= len; k++) {
                               if (matrix[i - k][j] == '1' && matrix[i][j - k] == '1') l++;
                               else break;
                            }
                            f[i][j] = l * l;
                        }
                    }
                    if (f[i][j] > max) {
                        max = f[i][j];
                    }
                }
            }

            return max;
        }

    }
    public static void main(String[] args) {
        Solution s = new Solution();
        char[][] m = new char[][]{{'1','0','1','0','0'},{'1','0','1','1','1'},{'1','1','1','1','1'},{'1','0','0','1','0'}};

        int res = s.maximalSquare(m);
        System.out.println(res);
    }
}
